package dp;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个下标从 0 开始的字符串数组 words ，和一个下标从 0 开始的 二进制 数组 groups ，两个数组长度都是 n 。
 * 你需要从 words 中选出 最长子序列。如果对于序列中的任何两个连续串，二进制数组 groups 中它们的对应元素不同，则 words 的子序列是不同的。
 * 正式来说，你需要从下标 [0, 1, ..., n - 1] 中选出一个 最长子序列 ，将这个子序列记作长度为 k 的 [i0, i1, ..., ik - 1] ，对于所有满足 0 <= j < k - 1 的 j 都有 groups[ij] != groups[ij + 1] 。
 * 请你返回一个字符串数组，它是下标子序列 依次 对应 words 数组中的字符串连接形成的字符串数组。如果有多个答案，返回 任意 一个。
 * 注意：words 中的元素是不同的 。
 * <p>
 * 示例 1：
 * 输入：words = ["e","a","b"], groups = [0,0,1]
 * 输出：["e","b"]
 * 解释：一个可行的子序列是 [0,2] ，因为 groups[0] != groups[2] 。
 * 所以一个可行的答案是 [words[0],words[2]] = ["e","b"] 。
 * 另一个可行的子序列是 [1,2] ，因为 groups[1] != groups[2] 。
 * 得到答案为 [words[1],words[2]] = ["a","b"] 。
 * 这也是一个可行的答案。
 * 符合题意的最长子序列的长度为 2 。
 * <p>
 * 示例 2：
 * 输入：words = ["a","b","c","d"], groups = [1,0,1,1]
 * 输出：["a","b","c"]
 * 解释：一个可行的子序列为 [0,1,2] 因为 groups[0] != groups[1] 且 groups[1] != groups[2] 。
 * 所以一个可行的答案是 [words[0],words[1],words[2]] = ["a","b","c"] 。
 * 另一个可行的子序列为 [0,1,3] 因为 groups[0] != groups[1] 且 groups[1] != groups[3] 。
 * 得到答案为 [words[0],words[1],words[3]] = ["a","b","d"] 。
 * 这也是一个可行的答案。
 * 符合题意的最长子序列的长度为 3 。
 *
 * @author Jisheng Huang
 * @version 20250505
 */
public class LongestSubsequence_2900 {
    /**
     * 注意 groups 中只有 0 和 1。
     * 例如示例 2 的 1011 有 3 个连续相同段 1,0,11，对应的最长子序列的长度为 3。每一段选一个下标，从 words 中得到对应的字符串，加入答案。
     * 一般地，形如 000111000111⋯ 中的每一个连续相同段只能选一个下标。为了让子序列尽量长，每个连续相同段都必须选一个下标。
     *
     * @param words  the given string array
     * @param groups the given integer array
     * @return list of words that satisfies the condition
     */
    public static List<String> getLongestSubsequence(String[] words, int[] groups) {
        List<String> ans = new ArrayList<>();
        int n = words.length;

        for (int i = 0; i < n; ++i) {
            if (i == n - 1 || groups[i] != groups[i + 1]) {
                ans.add(words[i]);
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        String[] words = {"e", "a", "b"};
        int[] groups = {0, 0, 1};

        System.out.println(getLongestSubsequence(words, groups));

        words = new String[]{"a", "b", "c", "d"};
        groups = new int[]{1, 0, 1, 1};

        System.out.println(getLongestSubsequence(words, groups));
    }
}
